Search results for "Euclidean shortest path"

showing 3 items of 3 documents

The computational complexity of the relative robust shortest path problem with interval data

2004

Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.

Discrete mathematicsInformation Systems and ManagementGeneral Computer ScienceManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringLongest path problemWidest path problemEuclidean shortest pathShortest Path Faster AlgorithmTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYModeling and SimulationShortest path problemK shortest path routingCanadian traveller problemDistanceMathematicsofComputing_DISCRETEMATHEMATICSMathematicsEuropean Journal of Operational Research
researchProduct

A class of label-correcting methods for the K shortest paths problem

2001

In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1. some label-correct…

Discrete mathematicsManagement Science and Operations ResearchComputer Science ApplicationsEuclidean shortest pathShortest Path Faster AlgorithmSettore SECS-S/06 -Metodi Mat. dell'Economia e d. Scienze Attuariali e Finanz.Shortest path problemK shortest path routingCanadian traveller problemYen's algorithmConstrained Shortest Path FirstDistanceK shortest paths problem label correcting methodsMathematics
researchProduct

The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

2016

Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm so…

Discrete mathematicsta113Mathematical optimizationSpanning treesocial network analysisComputer scienceAtlas algorithm020206 networking & telecommunications02 engineering and technologyLongest path problemverkostoanalyysiWidest path problemOdnoklassnikiEuclidean shortest pathShortest Path Faster Algorithmsocial graph020204 information systemsShortest path problem0202 electrical engineering electronic engineering information engineeringK shortest path routingCanadian traveller problemshortest path problemMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct